googologywikiaorg-20200223-history
User blog:Allam948736/Last digits of tetrations - proof
Since December, I have been at the center of a whole discussion on this wiki about how to compute the last digits of tetrations. It started when I added examples of first and last digits of tetrations to the article only to watch them get removed, and it was found that the original description was generally wrong. However, it does work in the case of b=10, which I assumed in the results I tried to add to the article. More recently, I proposed another method for computing last digits of \(x \uparrow\uparrow y\) which should produce correct results in all bases: \(s_0 = 1\) \(s_{n+1} = x^{s_n \mod \phi(b^d)} \mod lcm(b^d, \phi(b^d))\) Repeat until you reach \(s_y\) and take the final value mod \(b^d\) to obtain the last \(d\) digits of \(x \uparrow\uparrow y\) in base \(b\) for positive integers x and y. I tested this for a few cases for b=10 and got the same results I obtained using the basic recursive modular exponentiation method described in the original article prior to December (..98615075353432948736 for x=2 and y >= 22, ...04575627262464195387 for x=3 and y >= 21). For a proof of why this should work, continue reading. Statement: The last \(d\) base-\(c\) digits of \(^ba\) can be computed using the method given above. Proof: Let \(a\), \(b\), \(c\), and \(d\) be positive integers such that \(a\) is not a multiple of \(c\), and c cannot be expressed as \(m^n\) for positive integers \(m\) and \(n\) (that is, \(c\) is not a perfect power). Assume \(a\) and \(c\) are coprime. Then, \(a^b\) must also be coprime to \(c\), ruling out any possibilities of \(a^b \mod c\) that share common divisors with \(c\). The number of possibilities remaining for the last base-c digit of \(a^b\) is at most \(\phi©\) by definition of Euler's totient function. If the last base-c digit of \(a^b\) repeats sooner, the period will always be a divisor of \(\phi©\). Assume \(a\) and \(c\) are not coprime. Let \(q = gcd(a, c)\). Since \(q\) divides \(a^b\), the period of the last base-c digit can be no more than \(\phi(c/q)\), which is always a divisor of \(\phi©\). This is because the problem merely reduces to finding the period of \(a^b \mod (c/q)\), since q divides both c and a. If the last digit repeats sooner, the period will always be a divisor of \(\phi©\). Since I have proven the statement under both possibilities for 1 base-c digit, I will now prove the statement for more base-c digits. Once again, if \(a\) and \(c\) are coprime, then \(a\) and \(c^2\) are also coprime. Thus, \(a^b \mod c^2\) will always be coprime to \(c^2\), leaving at most \(\phi(c^2) = \phi©*c\) possibilities for the last 2 base-c digits of \(a^b\). Assume, once again, \(a\) and \(c\) are not coprime. Let \(q = gcd(a, c)\). Since \(q\) necessarily divides \(a^b\), the period of the last 2 base-c digits can be no more than \(\phi((c/q)^2)\), which is always a divisor of \(\phi(c^2)\). This is because \(a^b\) is always divisible by \(q^2\) for \(b \ge 2\), and so the problem reduces to finding the period of \(a^b \mod (c/q)^2\). We can continue proving this for more digits, but now for the good part. Since the period of the last \(d\) base-c digits of \(a^b\) can be no more than \(\phi(c^d)\), the last \(d\) base-c digits of \(a^b\) must coincide with those of \(a^{b \mod \phi(c^d)}\). After taking the exponent mod \(\phi(c^d)\) and substituting this for b, instead of taking \(a^b \mod c^d\), we take \(a^b \mod lcm(c^d, \phi(c^d))\), since \(\phi(c^d)\) does not always divide \(c^d\) itself, however, by definition, \(lcm(c^d, \phi(c^d))\) is divisible by \(\phi(c^d)\), meaning the last digits of \(a \uparrow\uparrow b\) in base c coincide with those of \(a^{a \uparrow\uparrow (b-1) \mod lcm(c^d, \phi(c^d))}\). Substitute the \(x\) from earlier for \(a\), \(y\) for \(b\), the \(b\) from earlier (not the \(b\) used in the proof) for \(c\), and replace (\(a \uparrow\uparrow b\) with \(s_n\), and you will have the expression \(s_{n+1} = x^{s_n \mod \phi(b^d)} \mod lcm(b^d, \phi(b^d))\) seen earlier. Therefore, the last digits of tetrations can be computed using the method I propose. Category:Blog posts